#include <stdlib.h>
#include "PQ.h"

static Item *pq;
static int N;

void PQinit(int maxN){
    pq = malloc(maxN * sizeof(Item));
    N = 0;
}

int PQempty(){
    return N == 0;
}

/**
 * PQinsert
 * -----------
 * 思路：
 * 从数组末尾开始查找，将大于v的元素依次向后移动一位；
 * - 如果pq[i]比v大，说明v插入的位置比i小，此时把pq[i]向后挪一个位置；
 * - 如果pq[i]比v小，说明v插入的位置在i+1
 */
void PQinsert(Item v){
    //记录v要插入位置的索引
    int i;
    for (i = N; i > 0; i--) {
        if (less(v, pq[i-1])) {
            pq[i] = pq[i-1];
        }else {
            break;
        }
    }
    pq[i] = v;
    N++;
}

Item PQdelmax(){
    return pq[--N];
}